{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a8b892c8",
   "metadata": {},
   "source": [
    "Printed and electronic copies of *Modeling and Simulation in Python* are available from [No Starch Press](https://nostarch.com/modeling-and-simulation-python) and [Bookshop.org](https://bookshop.org/p/books/modeling-and-simulation-in-python-allen-b-downey/17836697?ean=9781718502161) and [Amazon](https://amzn.to/3y9UxNb)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "early-drove",
   "metadata": {},
   "source": [
    "# Under the Hood"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "imported-table",
   "metadata": {
    "tags": []
   },
   "source": [
    "*Modeling and Simulation in Python*\n",
    "\n",
    "Copyright 2021 Allen Downey\n",
    "\n",
    "License: [Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-nc-sa/4.0/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "approximate-working",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# download modsim.py if necessary\n",
    "\n",
    "from os.path import basename, exists\n",
    "\n",
    "def download(url):\n",
    "    filename = basename(url)\n",
    "    if not exists(filename):\n",
    "        from urllib.request import urlretrieve\n",
    "        local, _ = urlretrieve(url, filename)\n",
    "        print('Downloaded ' + local)\n",
    "    \n",
    "download('https://raw.githubusercontent.com/AllenDowney/' +\n",
    "         'ModSimPy/master/modsim.py')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "suspended-occasion",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# import functions from modsim\n",
    "\n",
    "from modsim import *"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "younger-bullet",
   "metadata": {},
   "source": [
    "In this appendix we \"open the hood,\" looking more closely at how some of\n",
    "the tools we have used work: specifically, `run_solve_ivp`, `root_scalar`, and `maximize_scalar`.\n",
    "\n",
    "Most of the time you don't need to know, you can use these methods without knowing much about how they work.\n",
    "But there are a few reasons you might *want* to know.\n",
    "\n",
    "One reason is pure curiosity. \n",
    "If you use these methods, and especially if you come to rely on them, you might find it unsatisfying to treat them as black boxes. \n",
    "In that case, you might enjoy opening the hood.\n",
    "\n",
    "Another is that these methods are not infallible; sometimes things go wrong. \n",
    "If you know how they work, at least in a general sense, you might find it easier to debug them.\n",
    "\n",
    "And if nothing else, I have found that I can remember how to use these tools more easily because I know something about how they work."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "african-collector",
   "metadata": {},
   "source": [
    "## How run_solve_ivp Works\n",
    "\n",
    "`run_solve_ivp` is a function in the ModSimPy library that checks for common errors in the parameters and then calls `solve_ivp`, which is the function in the SciPy library that does the actual work.\n",
    "\n",
    "By default, `solve_ivp` uses the *Dormand-Prince method*, which is a kind of *Runge-Kutta method*. You can read about it at\n",
    "<https://en.wikipedia.org/wiki/Dormand-Prince_method>, but I'll give you a sense of\n",
    "it here.\n",
    "\n",
    "The key idea behind all Runge-Kutta methods is to evaluate the slope function several times at each time step and use a weighted average of the computed slopes to estimate the value at the next time step.\n",
    "Different methods evaluate the slope function in different places and compute the average with different weights.\n",
    "\n",
    "So let's see if we can figure out how `solve_ivp` works.\n",
    "As an example, we'll solve the following differential equation:\n",
    "\n",
    "$$\\frac{dy}{dt}(t) = y \\sin t$$\n",
    "\n",
    "Here's the slope function we'll use:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "coastal-cameroon",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "def slope_func(t, state, system):\n",
    "    y, = state\n",
    "    dydt = y * np.sin(t)\n",
    "    return dydt"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "egyptian-inventory",
   "metadata": {},
   "source": [
    "I'll create a `State` object with the initial state and a `System` object with the end time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "recovered-makeup",
   "metadata": {},
   "outputs": [],
   "source": [
    "init = State(y=1)\n",
    "system = System(init=init, t_end=3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "resident-document",
   "metadata": {},
   "source": [
    "Now we can call `run_solve_ivp`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "younger-affect",
   "metadata": {},
   "outputs": [],
   "source": [
    "results, details = run_solve_ivp(system, slope_func)\n",
    "details"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "sophisticated-person",
   "metadata": {},
   "source": [
    "One of the variables in `details` is `nfev`, which stands for \"number of function evaluations\", that is, the number of times `solve_ivp` called the slope function.\n",
    "This example took 50 evaluations.\n",
    "Keep that in mind.\n",
    "\n",
    "Here are the first few time steps in `results`: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "suspended-tumor",
   "metadata": {},
   "outputs": [],
   "source": [
    "results.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "removable-queens",
   "metadata": {},
   "source": [
    "And here is the number of time steps."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "noticed-portable",
   "metadata": {},
   "outputs": [],
   "source": [
    "len(results)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "unable-visibility",
   "metadata": {},
   "source": [
    "`results` contains 101 points that are equally spaced in time.\n",
    "Now you might wonder, if `solve_ivp` ran the slope function 50 times, how did we get 101 time steps?\n",
    "\n",
    "To answer that question, we need to know more about how the solver works.\n",
    "There are actually three stages:\n",
    "\n",
    "1. For each time step, `solve_ivp` evaluates the slope function seven times, with different values of `t` and `y`.\n",
    "\n",
    "2. Using the results, it computes the best estimate for the value `y` at the next time step.\n",
    "\n",
    "3. After computing all of the time steps, it uses interpolation to compute equally spaced points that connect the estimates from the previous step.\n",
    "\n",
    "To show the first two steps, I'll modify the slope function so that every time it runs, it adds the values of `t`, `y`, and `dydt` to a list called `evals`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "efficient-aluminum",
   "metadata": {},
   "outputs": [],
   "source": [
    "def slope_func(t, state, system):\n",
    "    y, = state\n",
    "    dydt = y * np.sin(t)\n",
    "    evals.append((t, y, dydt))\n",
    "    return dydt"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "compliant-sampling",
   "metadata": {},
   "source": [
    "Before we call `run_solve_ivp`, I'll initialize `evals` with an empty list.\n",
    "And I'll use the keyword argument `dense_output=False`, which skips the interpolation step and returns time steps that are not equally spaced (that is, not \"dense\")."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "handed-gothic",
   "metadata": {},
   "outputs": [],
   "source": [
    "evals = []\n",
    "results2, details = run_solve_ivp(system, slope_func, dense_output=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "mathematical-terrace",
   "metadata": {},
   "source": [
    "Here are the results:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "accessory-wrapping",
   "metadata": {},
   "outputs": [],
   "source": [
    "results2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "worth-baseline",
   "metadata": {},
   "source": [
    "Because we skipped the interpolation step, we can see that `solve_ivp` computed only seven time steps, not including the initial condition.\n",
    "Also, we see that the time steps are different sizes. \n",
    "The first is only 100 microseconds, the second is about 10 times bigger, and the third is 10 times bigger than that.\n",
    "\n",
    "The time steps are not equal because the Dormand-Prince method is *adaptive*.\n",
    "At each time step, it computes two estimates of the next\n",
    "value. By comparing them, it can estimate the magnitude of the error,\n",
    "which it uses to adjust the time step. If the error is too big, it uses\n",
    "a smaller time step; if the error is small enough, it uses a bigger time\n",
    "step. By adjusting the time step in this way, it minimizes the number\n",
    "of times it calls the slope function to achieve a given level of\n",
    "accuracy.\n",
    "In this example, it takes five steps to simulate the first second, but then only two more steps to compute the remaining two seconds."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "rapid-parks",
   "metadata": {},
   "source": [
    "Because we saved the values of `y` and `t`, we can plot the locations where the slope function was evaluated.\n",
    "I'll need to use a couple of features we have not seen before, if you don't mind.\n",
    "\n",
    "First we'll unpack the values from `evals` using `np.transpose`.\n",
    "Then we can use trigonometry to convert the slope, `dydt`, to components called `u` and `v`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "indie-antigua",
   "metadata": {},
   "outputs": [],
   "source": [
    "t, y, slope = np.transpose(evals)\n",
    "theta = np.arctan(slope)\n",
    "u = np.cos(theta)\n",
    "v = np.sin(theta)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "sublime-significance",
   "metadata": {},
   "source": [
    "Using these values, we can generate a *quiver plot* that shows an arrow for each time the slope function ran.\n",
    "The location of each arrow represents the values of `t` and `y`; the orientation of the arrow shows the slope that was computed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "fossil-librarian",
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "plt.quiver(t, y, u, v, pivot='middle', \n",
    "           color='C1', alpha=0.4, label='evaluation points')\n",
    "results2['y'].plot(style='o', color='C0', label='solution points')\n",
    "results['y'].plot(lw=1, label='interpolation')\n",
    "\n",
    "decorate(xlabel='Time (t)',\n",
    "         ylabel='Quantity (y)')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "uniform-cable",
   "metadata": {},
   "source": [
    "In this figure, there are 50 arrows, one for each time the slope function was evaluated, and 8 dots, one for each time step (although several of them overlap).\n",
    "The line shows the 101 points in the interpolation that connects the estimates.\n",
    "\n",
    "Notice that many of the arrows do not fall on the line; `solve_ivp` evaluated the slope function at these locations in order to compute the solution, but as it turned out, they are not part of the solution.\n",
    "\n",
    "This is good to know when you are writing a slope function; you should not assume that the time and state you get as input variables are correct."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "split-arabic",
   "metadata": {},
   "source": [
    "## How root_scalar Works\n",
    "\n",
    "`root_scalar` in the ModSim library is a wrapper for a function in the SciPy library with the same name.\n",
    "Like `run_solve_ivp`, it checks for common errors and changes some of the parameters in a way that makes the SciPy function easier to use (I hope).\n",
    "\n",
    "According to the documentation, `root_scalar` uses \"a combination of bisection, secant, and inverse quadratic interpolation methods.\" (See\n",
    "<https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.root_scalar.html>)\n",
    "\n",
    "To understand what that means, suppose we're trying to find a root of a\n",
    "function of one variable, $f(x)$, and assume we have evaluated the\n",
    "function at two places, $x_1$ and $x_2$, and found that the results have\n",
    "opposite signs. Specifically, assume $f(x_1) > 0$ and $f(x_2) < 0$, as\n",
    "shown in the following diagram:\n",
    "\n",
    "![Initial state of a root-finding search](https://github.com/AllenDowney/ModSim/raw/main/figs/secant.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "divided-sailing",
   "metadata": {},
   "source": [
    "If $f$ is a continuous function, there must be at least one root in this\n",
    "interval. In this case we would say that $x_1$ and $x_2$ *bracket* a\n",
    "root.\n",
    "\n",
    "If this were all you knew about $f$, where would you go looking for a\n",
    "root? If you said \"halfway between $x_1$ and $x_2$,\" congratulations!\n",
    "`You just invented a numerical method called *bisection*!\n",
    "\n",
    "If you said, \"I would connect the dots with a straight line and compute\n",
    "the zero of the line,\" congratulations! You just invented the *secant\n",
    "method*!\n",
    "\n",
    "And if you said, \"I would evaluate $f$ at a third point, find the\n",
    "parabola that passes through all three points, and compute the zeros of\n",
    "the parabola,\" congratulations, you just invented *inverse quadratic\n",
    "interpolation*!\n",
    "\n",
    "That's most of how `root_scalar` works. The details of how these methods are\n",
    "combined are interesting, but beyond the scope of this book. You can\n",
    "read more at <https://en.wikipedia.org/wiki/Brents_method>."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dental-archives",
   "metadata": {},
   "source": [
    "## How maximize_scalar Works \n",
    "\n",
    "`maximize_scalar` in the ModSim library is a wrapper for a function in the SciPy library called `minimize_scalar`.\n",
    "You can read about it at <https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize_scalar.html>.\n",
    "\n",
    "By default, it uses Brent's method, which is related to the method I described in the previous section for root-finding.\n",
    "Brent's method for finding a maximum or minimum is based on a simpler algorithm:\n",
    "the *golden-section search*, which I will explain.\n",
    "\n",
    "Suppose we're trying to find the minimum of a function of a single variable, $f(x)$.\n",
    "As a starting place, assume that we have evaluated the function at three\n",
    "places, $x_1$, $x_2$, and $x_3$, and found that $x_2$ yields the lowest\n",
    "value. The following diagram shows this initial state.\n",
    "\n",
    "![Initial state of a golden-section\n",
    "search](https://github.com/AllenDowney/ModSim/raw/main/figs/golden1.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "alpine-metro",
   "metadata": {},
   "source": [
    "We will assume that $f(x)$ is continuous and *unimodal* in this range,\n",
    "which means that there is exactly one minimum between $x_1$ and $x_3$.\n",
    "\n",
    "The next step is to choose a fourth point, $x_4$, and evaluate $f(x_4)$.\n",
    "There are two possible outcomes, depending on whether $f(x_4)$ is\n",
    "greater than $f(x_2)$ or not.\n",
    "The following figure shows the two possible states.\n",
    "\n",
    "![](https://github.com/AllenDowney/ModSim/raw/main/figs/golden2.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "african-check",
   "metadata": {},
   "source": [
    "If $f(x_4)$ is less than $f(x_2)$ (shown on the left), the minimum must\n",
    "be between $x_2$ and $x_3$, so we would discard $x_1$ and proceed with\n",
    "the new bracket $(x_2, x_4, x_3)$.\n",
    "\n",
    "If $f(x_4)$ is greater than $f(x_2)$ (shown on the right), the local\n",
    "minimum must be between $x_1$ and $x_4$, so we would discard $x_3$ and\n",
    "proceed with the new bracket $(x_1, x_2, x_4)$.\n",
    "\n",
    "Either way, the range gets smaller and our estimate of the optimal value\n",
    "of $x$ gets better.\n",
    "\n",
    "This method works for almost any value of $x_4$, but some choices are\n",
    "better than others. You might be tempted to bisect the interval between\n",
    "$x_2$ and $x_3$, but that turns out not to be optimal. You can\n",
    "read about a better option at <https://greenteapress.com/matlab/golden>."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "broken-preparation",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Tags",
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
